def get_res(steel_length, baseline_length_list, method):
    res = []
    if steel_length < sum(baseline_length_list):
        print("钢筋长度不满足让所有规格的短料都至少各截一根")
        res = None
        return res
    elif method == "trace_back":  # 回溯
        cur_length = steel_length - sum(baseline_length_list)
        path = []
        min_path = []
        min_len_list = [cur_length]
        trace_back(cur_length, baseline_length_list, path, min_path, min_len_list)
        # print(min_len_list)
        # print(min_path)
        res_len = min_len_list[0]
        res_map = {}
        for key in baseline_length_list:
            res_map[key] = 1
        for key in min_path:
            res_map[key] += 1
        print(res_map)
        res.extend([res_len, res_map])
        return res
    elif method == "dynamic_programming":  # 动态规划
        cur_length = steel_length - sum(baseline_length_list)
        dp_list = dp(baseline_length_list, cur_length)
        print(dp_list)
        res_map = {}
        for key in baseline_length_list:
            res_map[key] = 1
        cursor = cur_length
        while cursor >= 0:
            cur_key = baseline_length_list[0]
            for key in baseline_length_list:
                if cursor - key >= 0:
                    if dp_list[cursor - key] == dp_list[cur_length]:
                        res_map[key] += 1
                        cur_key = key
                        break
            cursor = cursor - cur_key
        res = [dp_list[cur_length], res_map]
        # print(res_map)
        # print(cur_length)
        # print(dp_list[cur_length])
        return res
    else:
        res = None
        print("方法不存在")
    return res


def trace_back(cur_length, baseline_length_list, path, min_path, min_len_list):
    if cur_length < min(baseline_length_list):
        if cur_length < min_len_list[0]:
            min_len_list[0] = cur_length
            min_path.clear()
            for item in path:
                min_path.append(item)
        return
    for baseline_length in baseline_length_list:
        if cur_length >= baseline_length:
            cur_length -= baseline_length
            path.append(baseline_length)
            trace_back(cur_length, baseline_length_list, path, min_path, min_len_list)
            cur_length += baseline_length
            path.pop()
    return


def dp(baseline_length_list, cur_length):
    dp_list = []
    for i in range(min(baseline_length_list)):
        dp_list.append(i)
    for i in range(min(baseline_length_list), cur_length + 1): # [29, 600 - (69 + 39 + 29)]
        min_val = dp_list[i - min(baseline_length_list)]
        for j in baseline_length_list:
            if i - j >= 0:
                min_val = min(min_val, dp_list[i - j])
        dp_list.append(min_val)
    return dp_list


def print_res(res, baseline_length_list):
    print("截取长度", end="")
    for i in range(len(baseline_length_list)):
        if i != len(baseline_length_list) - 1:
            print(str(baseline_length_list[i]) + "cm，",end="")
        else:
            print(str(baseline_length_list[i]) + "cm",end="")
    print("不同长度的短料", end="")
    for i in range(len(baseline_length_list)):
        if i != len(baseline_length_list) - 1:
            print(str(baseline_length_list[i]) + "cm:" + str(res[1][baseline_length_list[i]]) + "根，", end="")
        else:
            print(str(baseline_length_list[i]) + "cm:" + str(res[1][baseline_length_list[i]]) + "根", end="")
    print()
    print("剩余：" + str(res[0]) + "cm")


if __name__ == "__main__":
    steel_length = int(eval(input("请输入钢筋长度（m）：")) * 100)
    baseline_length_list = [69, 39, 29]
    res = get_res(steel_length, baseline_length_list, "dynamic_programming")
    print_res(res, baseline_length_list)